home *** CD-ROM | disk | FTP | other *** search
/ Chip 1996 April / CHIP 1996 aprilis (CD06).zip / CHIP_CD06.ISO / hypertxt.arj / 9311 / CHIPKEDD.CD < prev    next >
Text File  |  1995-04-15  |  9KB  |  150 lines
  1.           @VSzerencsés vezérek@N
  2.           
  3.           Augusztusi  számunk  feladatainak  megoldásairól  ejtünk  az
  4.           alábbiakban néhány szót.
  5.           
  6.           
  7.           De   ezt   megelôzôen   egy   helyesbítést   kell   tennünk:
  8.           szeptemberi   számunkban   tévesen   jelent   meg   júniusi,
  9.           Tili-toli  címû  feladatunk megoldóinak névsora. Tehát immár
  10.           helyesen:   a  feladatra  Déri  Attila  és  Verbôczi  Zoltán
  11.           küldött  be  jó  megoldást. Az érintettektôl és olvasóinktól
  12.           elnézést kérünk.
  13.           
  14.           
  15.            @VSzerencsés számok@N
  16.           
  17.           Egy  számot  akkor  neveztünk  szerencsésnek,  ha jegyei két
  18.           csoportba  oszthatók  úgy,  hogy  a  két csoportban a számok
  19.           összege   ugyanannyi,   mint   például   a   32843  esetében
  20.           (8+2=3+4+3).   A   feladat   az  ""iker"  (azaz  szomszédos)
  21.           szerencsés    számokat   megkeresô   program   írása   volt.
  22.           Megoldásként  hét  programot  kaptunk  hat  megfejtônktôl. A
  23.           Pascal  fölénye megkérdôjelezhetetlen, bár mérséklôdött: 4-3
  24.           arányban  nyert  a  C elôtt. Természetesen egyéb különbségek
  25.           is  adódtak  a  megoldásokban.  A többség képenyôre íratta a
  26.           megoldásokat,  de  volt,  aki  file-ba  (Verbôczi Zoltán); a
  27.           többség  százezerig  kereste meg a kívánt számokat, de volt,
  28.           aki   kilencjegyû  számokat  is  megtalált  programjával  (a
  29.           Bonifert-Fürcht  páros programjai); a többség megoldásai nem
  30.           mérhetô   idô  alatt  (pontosabban  csak  ""kiírásnyi"  idôt
  31.           használva)   varázsolták  elô  az  ikreket,  de  volt  olyan
  32.           program   is,  amely  négy  óra  alatt  számolt  (volna)  el
  33.           százezerig  --  igaz  hibátlanul,  ellentétben  más,  némely
  34.           ikerpárost ""elfelejtô" programmal.
  35.           
  36.           Egy  picit  utánagondolva  a  feltételeknek,  rögtön adódik,
  37.           hogy  egy  szerencsés szám jegyeinek összege páros. Ebbôl az
  38.           is  hamar kitalálható, hogy az iker kisebbik tagjának utolsó
  39.           jegye  kilences, mivel a ""nagyobbik testvér" jegyösszegének
  40.           páros   volta  csak  így  biztosítható.  Ez  persze  azt  is
  41.           jelenti,  hogy  kétjegyû ikrek nem találhatók, sôt még az is
  42.           kiszámolható  fejben,  hogy  a  háromjegyû számok körében is
  43.           csak  egy  páros lesz: a 459 és az 550. Innen kezdve viszont
  44.           rohamosan  szaporodnak  az  iker  szerencsés számok (a hamar
  45.           megvizsgálható  százezres  határig 984 darab pár található).
  46.           Megtalálásukhoz      segítséget      nyújthatott     májusi,
  47.           részhalmazokról  szóló  feladatunk;  hiszen itt is nagyjából
  48.           arról   volt  szó,  hogy  a  számjegyek  sorozatának  minden
  49.           lehetséges  részsorozatát  képezve,  megkapjuk-e  az  összeg
  50.           felét.   Érdekes   eltérések   adódtak   a   programokban  a
  51.           számjegyek   elôállítási  módjában:  volt,  aki  matematikai
  52.           mûveleteket   (div,   mod)  használt;  volt  aki  stringekké
  53.           konvertálva  szeletelt;  s  volt, aki megfordítva a kérdést,
  54.           egy  tömbben tárolt jegyekbôl képezte a számokat (ez esetben
  55.           persze jobban oda kellett figyelni a megfelelô léptetésre).
  56.           
  57.           A   CT   Press   BBS-en  mindkét  nyelv  híveinek  található
  58.           megoldás:  Verbôczi  Zoltán Pascal, és Bonifert Csaba-Fürcht
  59.           Zoltán  C nyelven írott programja olvasható ott. A szerencse
  60.           --  egy  doboz  Tungsram  flopy  formájában  --  Déri Attila
  61.           olvasónkat vonta kegyeiben.
  62.           
  63.           
  64.            @VVezérek másképpen...@N
  65.           
  66.           ...címmel  megjelent  feladatunk  egy  olyan  program írását
  67.           kívánta  meg,  amely  elhelyez  a  8x8-as  sakktáblán  minél
  68.           kevesebb  királynôt  úgy,  hogy  azok a tábla minden mezôjét
  69.           ütés   alatt  tartsák.  A  megoldások  száma  ""mesés":  hét
  70.           megfejtônk  hét  programot küldött be (itt a Pascal kontra C
  71.           mérkôzés  eredménye  5-2  lett). Az tiviálisan adódik az egy
  72.           vezér  által maximálisan ""fogható" mezôk számából, hogy egy
  73.           illetve  két  vezér  nem lesz elegendô. Az is sejthetô, hogy
  74.           innen  kezdve  viszont  az  idô  lesz a szûk keresztmetszet:
  75.           hiszen  már három vezér is 41664 variációban helyezhetô el a
  76.           8x8-as  táblán,  de  négy vezér már 635376, öt pedig 7624512
  77.           lehetôséget  jelent.  Megfejtôink  jól  hidalták  át  ezt  a
  78.           nehézséget:   a   beküldött   programok   2-8   perc   alatt
  79.           szolgáltattak   egy-egy   megoldást  a  szükséges  öt  vezér
  80.           elhelyezésére  (386SX  gépen  futtatva). Ennél sokkal tovább
  81.           mûködött  Verbôczi  Zoltán  programja: ennek azonban az volt
  82.           az  oka, hogy nemcsak egy elrendezést adott meg, hanem az öt
  83.           vezér  összes megfelelô elhelyezését megkereste! (Ezek száma
  84.           4860  --  nem  véve  figyelembe  a  lehetséges tükrözéseket,
  85.           forgatásokat).
  86.           
  87.           Két  lehetséges megoldási utat ismertetünk olvasóink leírása
  88.           nyomán.  Déri  Attila:  ""Rekurzív  eljárással keresem meg a
  89.           királynôk   helyét.   Az   eljárás  a  legutoljára  lerakott
  90.           királynô  'utáni'  mezôbe  lerak  egy  királynôt, s megnézi,
  91.           hogy  minden  mezô fogott-e. Ha nem, és a lerakott királynôk
  92.           száma  nem  haladja  meg az eddigi minimumot, akkor meghívja
  93.           önmagát.  Ha  minden  mezô  ütés alatt áll, akkor elmenti az
  94.           állást.  A lerakott királynôt felveszi, s a következô mezôbe
  95.           téve,  újra  vizsgálja  az  állást  a  tábla végéig menve. A
  96.           rekurzív   eljárás  végén  a  program  kiírja  az  elmentett
  97.           állást."  Más  utat választott Horváth Sándor: ""A sakktábla
  98.           minden  mezôjéhez  egy  64  bites számot rendelhetünk, amely
  99.           jelzi,  hogy  onnan a tábla mely mezôi tarthatók ütés alatt.
  100.           (...)  E  számok  (64 db 64 bites érték) segítségével nagyon
  101.           könnyen  eldönthetô,  hogy a táblán elhelyezett néhány vezér
  102.           ütésben  tartja-e  az  egész  táblát:  a  vezérekhez tartozó
  103.           értékeket  a  logikai OR mûvelettel ""összeadjuk". Ha az így
  104.           kapott  64  bit  mindegyike  1-es, akkor a vezérek lefedik a
  105.           táblát.  (A  Pascalban igazi 64 bites egész típus nem lévén,
  106.           két  32  bites  longintbôl  kellett  összerakni egy 64 bites
  107.           ""számot").   Az   összes   eset   elôállításához  a  halmaz
  108.           részhalmazainak  elôállításánál  használt algoritmust vettem
  109.           át  egy az egyben (megint a májusi feladat!), melyhez egy 64
  110.           byte-os stringben tároltam a tábla elrendezését."
  111.           
  112.           A  CT  Press BBS-en Verbôczi Zoltán és Déri Attila programja
  113.           található  meg. Természetesen az eddigiekben név szerint nem
  114.           említett  megfejtôink  (Bonifert  Csaba-Fürcht  Zoltán, Tóth
  115.           László,  Balla  Attila)  is részesei az év végi sorsolásnak.
  116.           Végezetül a feladat egy megoldása: A2, C1, D6, D7, H1.
  117.           
  118.           @KBánhegyesi Zoltán@N
  119.           
  120.           
  121.           
  122.            @Vùj rejtvényünk@N
  123.           
  124.            @VMersenne-prímek@N
  125.           
  126.           A  Bild  der  Wissenschaft  tavaly novemberi számában jelent
  127.           meg  egy  híradás egy újabb prímrekordról: Michael Stromberg
  128.           megtalálta  az  eddig  ismert  legnagyobb  prímet,  amelynek
  129.           értéke
  130.           
  131.           2^756839-1.  Ezt  a  227832  jegyû  számot  magazinunk majd'
  132.           félévig  közölhetné  folyamatosan,  összes  oldalán!  Mint a
  133.           cikkbôl  is kiderül, Stromberg egy közel háromszázötven éves
  134.           úton   indult  el.  Mersenne  francia  matematikus  1644-ben
  135.           közölte, hogy a
  136.           
  137.           2^p-1  kifejezés értéke 1 < p < 258 számok esetén csak a p =
  138.           2,  3,  5, 7, 13, 17, 19, 31, 67, 127 és 257 értékénél prím.
  139.           A  matematikusok háromszáz év alatt tisztázták, hogy a lista
  140.           hibás:  tartalmaz  összetett  számokat,  s nem minden prímre
  141.           vezetô értéket adott meg Mersenne.
  142.           
  143.           A  feladat  egy  olyan  program  írása, mely háromszáz évnél
  144.           némileg  rövidebb  idô  alatt  megtalálja a hibákat Mersenne
  145.           listájában.
  146.           
  147.           Beküldési határidô: 1993 december 3.
  148.           
  149.           @KBánhegyesi Zoltán@N
  150.